
/*
 * Question: Try to travel a infix order threaded
 * binary tree from the first node to the last,
 * vice versa.
 *
 * Date: 01/27/2012
 */

#include <iostream>
#include "iofile.h"
#include "bthtree.h"
using namespace std;

class bithrtree : public _bitree<bithrtree, char>
{
};

void visit(bthtree *rt)
{
    cout << rt->key << " ";
}

void inorder_succ(bthtree *rt)
{
    bthtree *p;

    if (!rt)
        return;
    p = rt;
    while (p->ltag == BTT_LINK)
        p = p->lchild;
    while (p){
        visit(p);
        if (p->rtag == BTT_THREAD)
            p = p->rchild;
        else{
            p = p->rchild;
            while (p->ltag == BTT_LINK)
                p = p->lchild;
        }
    }
}

void inorder_pred(bthtree *rt)
{
    bthtree *p;

    if (!rt)
        return;
    p = rt;
    while (p->rtag == BTT_LINK)
        p = p->rchild;
    while (p){
        visit(p);
        if (p->ltag == BTT_THREAD)
            p = p->lchild;
        else{
            p = p->lchild;
            while (p->rtag == BTT_LINK)
                p = p->rchild;
        }
    }
}

int main()
{
    bthtree *rt;

    open_input("chap06/misc01.txt");
    bthtree_increate<bthtree, char>(rt);
    inorder_succ(rt);
    cout << endl;
    inorder_pred(rt);
    cout << endl;
    bthtree_destory(rt);
    close_input();
    return 0;
}
